package 中等.动态规划.子序列;

/**
 * 给你一个字符串 s ，它只包含三种字符 a, b 和 c 。
 * 请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-substrings-containing-all-three-characters/
 */
public class 包含所有三种字符的子字符串数目_1358 {

    public static void main(String[] args) {

        System.out.println(numberOfSubstrings("aaabc"));

    }

    /**
     * 统计以索引 i 结尾的子字符串同时包含a,b,c的总数目
     * 如果 [j,i] 使得三种字符均出现，那么 [0,j]的字符串一定符合条件
     */
    public static int numberOfSubstrings(String s) {
        int count = 0;
        char[] chars = s.toCharArray();
        for (int i = 2; i < chars.length; i++) {
            boolean[] record = new boolean[3];

            for (int j = i; j >= 0; j--) {
                record[chars[j] - 'a'] = true;
                if (record[0] && record[1] && record[2]) {
                    count += j + 1;
                    break;
                }
            }
        }

        return count;
    }

}
